#include <iostream>
#include <iterator>
#include <iomanip>
#include <algorithm>
#include <functional>

using namespace std;

namespace small {

enum side_t { LEFT_SIDE, RIGHT_SIDE };

template <class T>
struct superholder {
    superholder(const T &subholder, int number, side_t side):
        _subholder( subholder ), _number( number ), _side( side ) {}

    void print(side_t side) const {
        if( _side == side )
            cout << _number << " ";
        _subholder.print( side );
    }

private:
    const T &_subholder;
    const int _number;
    const side_t _side;
};

struct empty_holder {
    void print(side_t) const {}
};


int operations_number = 0;


template <int N, class T = empty_holder>
struct level {
    typedef superholder<T> next_holder;
    typedef level<N-1,next_holder> next_level;

    static void put_right(const int *a, int restl, int restr, const T &holder = empty_holder()) {
        operations_number++;
        next_level::search( a+1, restl, restr - *a, next_holder( holder, *a, RIGHT_SIDE ) ); }

    static void put_left(const int *a, int restl, int restr, const T &holder = empty_holder()) {
        operations_number++;
        next_level::search( a+1, restl - *a, restr, next_holder( holder, *a, LEFT_SIDE ) ); }

    static void search(const int *a, int restl, int restr, const T &holder) {
        if( *a <= restr )
            put_right( a, restl, restr, holder );
        if( *a <= restl )
            put_left( a, restl, restr, holder );
    }
};


template <class T>
struct level<0,T> {
    static void search(const int *a, int restl, int restr, const T &holder)
    {
        holder.print( LEFT_SIDE ); cout << ": "; holder.print( RIGHT_SIDE );
        cout << " (" << operations_number << ")" << endl;
    }
};


template <int N> int sum(const int *a) { return *a + sum<N-1>( a + 1 ); };
template <> int sum<0>(const int *) { return 0; }

template <class T, int N>
static void search(T (&a)[N])
{
    operations_number = 0;

    int const halfsum = sum<N>( a )/2;
    sort( a, a+N, greater<int>() );
    level<N>::put_right( a, halfsum, halfsum );
    cout << "total operations: " << operations_number << endl;
    cout << endl;
}

int test_06[] = { 62, 83, 121, 281, 305, 486 };
int test_06b[] = { 10062, 10083, 10121, 10281, 10305, 10486 };
int test_07[] = { 62, 83, 121, 281, 429, 486, 734 };
int test_08[] = { 62, 83, 121, 281, 342, 486, 734, 771 };
int test_09[] = { 62, 83, 121, 281, 486, 512, 734, 771, 854 };
int test_10[] = { 62, 83, 121, 281, 373, 486, 734, 771, 854, 885 };
int test_11[] = { 62, 83, 121, 281, 486, 548, 734, 771, 854, 885, 921 };
int test_12[] = { 62, 83, 121, 281, 427, 486, 734, 771, 854, 885, 921, 975 };
int test_13[] = { 62, 83, 121, 281, 486, 573, 734, 771, 854, 885, 921, 975, 1000 };
int test_14[] = { 62, 83, 121, 281, 486, 538, 734, 771, 854, 885, 921, 975, 1000, 1111 };


int full_search()
{
    search( test_06 );
    search( test_06b );
    search( test_07 );
    search( test_08 );
    search( test_09 );
    search( test_10 );
    search( test_11 );
    search( test_12 );
    search( test_13 );
    search( test_14 );

    return 0;
}

} // namespace small
